package com.leetcode.algs4.string;

/**
 * @author Dennis Li
 * @date 2020/7/9 21:54
 */
public class PatternMatch {
    public static int search(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();

        for (int i = 0; i <= N - M; i++) {
            int j;
            // j 主要是用来遍历模式串
            for (j = 0; j < M; j++) {
                if (txt.charAt(i + j) != pat.charAt(j)) break;
            }
            if (j == M) return i;
        }
        return N;
    }

    public static int search2(String pat, String txt) {
        int j, M = pat.length();
        int i, N = txt.length();

        for (i = 0, j = 0; i < N && j < M; i++) {
            if (txt.charAt(i) == pat.charAt(j)) j++;
            else {
                i -= j; // 如果在这个位置匹配失败，那么i可以直接移步到这个位置，而不是往后进一位
                j = 0;
            }
        }
        return j == M ?
                i - M : // 找到匹配
                N; // 未找到匹配
    }
}
